package org.lql.algo.codecrush.week010;

import org.lql.algo.common.ListNode;
import org.lql.algo.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 15:28
 * @description: 面试题 04.03. 特定深度节点链表 <a href="https://leetcode.cn/problems/list-of-depth-lcci/description/">...</a>
 **/
public class ListOfDepth {

	public ListNode[] listOfDepth(TreeNode tree) {
		if (tree == null) return new ListNode[0];

		List<ListNode> result = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(tree);

		while (!queue.isEmpty()) {
			int size = queue.size();
			ListNode dummy = new ListNode(-1); // 虚拟头节点
			ListNode curr = dummy;

			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();

				// 构造链表
				curr.next = new ListNode(node.val);
				curr = curr.next;

				// 加入下一层
				if (node.left != null) queue.offer(node.left);
				if (node.right != null) queue.offer(node.right);
			}
			result.add(dummy.next); // 本层链表头
		}

		return result.toArray(new ListNode[0]);
	}
}
